package leecode

import "fmt"

func CountSubmatrices(grid [][]int, k int) int {
	prefix := make([][]int, len(grid)+1)
	for i := 0; i < len(prefix); i++ {
		prefix[i] = make([]int, len(grid[0])+1)
	}
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
			prefix[i+1][j+1] = prefix[i][j+1] + prefix[i+1][j] - prefix[i][j] + grid[i][j]
		}
	}
	fmt.Println(prefix)
	var result int
	for i := 1; i < len(prefix); i++ {
		for j := 1; j < len(prefix[i]); j++ {
			if prefix[i][j] <= k {
				result++
			}
		}
	}
	return result
}
